package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-07-05 17:12
 */
public class 题库_0179_最大数 {

  static
  class Solution {
    public String largestNumber(int[] nums) {
      if (nums == null || nums.length == 0) {
        return null;
      }
      sort(nums);
      StringBuilder sb = new StringBuilder();
      for (int num : nums) {
        if (num == 0 && sb.length() == 0) {
          continue;
        }
        sb.append(num);
      }
      return sb.length() == 0 ? "0" : sb.toString();
    }

    private void sort(int[] nums) {

      for (int i = 1; i < nums.length; ++i) {
        int candidate = nums[i];
        int j = i - 1;
        while (j >= 0 && isGreaterThan(candidate, nums[j])) {
          nums[j + 1] = nums[j];
          --j;
        }
        nums[j + 1] = candidate;
      }

    }

    private boolean isGreaterThan(int candidate, int target) {
      String candidateString = String.valueOf(candidate);
      String targetString = String.valueOf(target);

      String num1 = candidateString + targetString;
      String num2 = targetString + candidateString;

      for (int i = 0; i < num1.length(); ++i) {
        if (num1.charAt(i) < num2.charAt(i)) {
          return false;
        } else if (num1.charAt(i) > num2.charAt(i)) {
          return true;
        }
      }
      return false;

    }
  }

}
